#include <fstream>
#include <sstream>
#include <iostream>
#include <stdexcept>

#include <cstring>
#include <cstdlib>


#include "Interpreter.h"
#include "Loader.h"

#define CHECK_TYPES           1
#define INSTRUCTION_TRACING   0
#define CALL_TRACING          0
#define DEBUG_GC              0

#include "macros.h"

using namespace std;


std::ostream& operator<<(std::ostream& os, const StackElem& p)
{
    switch (p.type)
    {
    case Undefined:
        os << "Undefined";
        break;
    case Number:
        os << "Num: " << p.value;
        break;
    case ObjRef:
        os << "Obj: " << p.object << " -> " << *(p.object);
        break;
    case ArrayRef:
        os << "Arr: " << p.array << " -> " << *(p.array);
        break;
    case StringRef:
    {
        string s = (*p.string)->size > 20
                    ? string((*p.string)->string, (*p.string)->string + 17) + string("...")
                    : string((*p.string)->string);
        os << "Str: \"" << s << "\"";
        break;
    }
    case ReturnAddress:
        os << "RetAddr: " << p.ret_addr;
        break;
    case FramePointer:
        os << "FramePtr: " << p.backup_fp;
        break;
    default:
        throw std::runtime_error("Cannot print an unknown type!");
    }
    return os;
}

const char Interpreter::fake_main_callsite[2] = { 2, 0 };
Bytecode const Interpreter::exit_pc = Interpreter::fake_main_callsite + 1;

Interpreter::Interpreter(const string& filename)
: stack(new StackElem[DefaultStackSize]),
  src_ref_table(new ObjectTableElem[DefaultHeapSize]),
  dst_ref_table(new ObjectTableElem[DefaultHeapSize]),
  obj_table(DefaultRefTableSize),
  allocs_since_gc(0),
  insns_since_gc(0),
  src_heap(new StackElem[DefaultHeapElems]),
  dst_heap(new StackElem[DefaultHeapElems])
{
    alloc_ptr = src_heap;
    memset(stack, 0, sizeof(stack[0]) * DefaultStackSize);
    memset(src_ref_table, 0, sizeof(src_ref_table[0]) * DefaultHeapSize);
    memset(dst_ref_table, 0, sizeof(src_ref_table[0]) * DefaultHeapSize);

    addr_to_name.insert(AddrToNameMap::value_type(Bytecode(-1), ""));
    addr_to_name.insert(AddrToNameMap::value_type(Bytecode(NULL), ""));

    Loader l(*this);
    l.LoadModule(filename);

    BindBuiltIns();

    obj_table_end = src_ref_table + DefaultHeapSize;
    stack_end = stack + DefaultStackSize;

    #if DEBUG_GC_TIME==1
        fDeletePart1Clock = 0;
        fDeletePart2Clock = 0;
        fRootSetSearchClock = 0;
        fSpaghettiPullingClock = 0;
        fRefTableCleanClock = 0;
        fTotalGCRuns = 0;
    #endif
}

Interpreter::~Interpreter()
{
    delete [] bytecode;
    delete [] stack;

    CleanRefTable();

    delete [] src_ref_table;
    delete [] dst_ref_table;
    delete [] src_heap;
    delete [] dst_heap;
}

bool Interpreter::ShouldPerformGC()
{
    // tady se da vyladit podminka, za jake se ma GC spustit
    return allocs_since_gc >= HeapAllocationsBeforeGC;
    //return fInstructionsSinceLastGC >= InstructionsBeforeGC;
}

void Interpreter::GC()
{
    #if DEBUG_GC==1
        cout << endl << "GC now taking place, standby..." << endl;
    #endif

    // 1. najdi root set, to rovnou prekopiruj do nove pameti...
    //    (root set jsou jen odkazy ze zasobniku - kdybychom meli globalni promenne, tak ty by tam patrily taky)
    // 2. zacni prochazet novou pamet: pokud je to objekt, pak projdi fieldy, pokud pole, tak polozky pole;
    //    oboji je StackElem; pokud je to ObjRef nebo ArrayRef, tak neco udelej s odkazovanou hodnotou
    //    TODO nezapomen updatovat pointery v ReferenceTable
    //    - idealne projit celou a pokud je odkazovany objekt presmerovany do nove haldy, zmenit pointer v tabulce, jinak
    //    nastavit pointer v tabulce na 0 - tim se to sice trochu vyfragmentuje, ale s tim uz si poradime
    // 3. az se dostanu na prvni volne misto, mam hotovo, starou heap smaz

    StackElem* lSP = stack;
    StackElem* lStackEnd = sp + 1;
    ObjectTableElem* const lNewHeap = dst_ref_table;
    ObjectTableElem* lNewHP = lNewHeap;

    // 1. faze - root set - projdu zasobnik a kdyz narazim na referenci na objekt nebo pole, prekopiruju objekt z puvodni haldy
    // na novou (pouze melka kopie) - taky musim davat pozor na to, abych nekopiroval neco, co uz jsem zkopiroval - typicky
    // se to muze stat v pripadech, kdy mam lokalni promennou typu reference na objekt a predavam ji do nejake funkce - pak budu
    // mit na zasobniku na dvou mistech referenci na tentyz objekt na halde

    #if DEBUG_GC_TIME==1
        clock_t lClockRootSet1 = clock();
    #endif

    while(lSP != lStackEnd)
    {
        if(lSP->type == ObjRef)
        {
            if(!(*lSP->object)->GCIsForwarded)
            {
                *lNewHP = **lSP->object;
                (*lSP->object)->GCIsForwarded = true;
                (*lSP->object)->GCForwardedTo = lNewHP;
                lNewHP++;
            }
        }
        else if(lSP->type == ArrayRef)
        {
            if(!(*lSP->array)->GCIsForwarded)
            {
                *lNewHP = **lSP->array;
                (*lSP->array)->GCIsForwarded = true;
                (*lSP->array)->GCForwardedTo = lNewHP;
                lNewHP++;
            }
        }
        else if(lSP->type == StringRef)
        {
            if(!(*lSP->string)->GCIsForwarded)
            {
                *lNewHP = **lSP->string;
                (*lSP->string)->GCIsForwarded = true;
                (*lSP->string)->GCForwardedTo = lNewHP;
                lNewHP++;
            }
        }

        lSP++;
    }

    #if DEBUG_GC_TIME==1
        clock_t lClockRootSet2 = clock();
        fRootSetSearchClock += (lClockRootSet2 - lClockRootSet1);
    #endif

    // 2. faze - tahani spaget z hrnce :-) :-) :-)
    // co tady budu delat: projdu novou haldu od zacatku; pokud je ulozeny objekt pole, projdu jeho polozky, pokud je to objekt, tak
    // fieldy; pokud je prislusna hodnota referenci na objekt, tak ji zkopiruju ze stare haldy na novou (jestli tam jeste neni),
    // pricemz pro umistovani kopirovanych objektu pouzivam lNewHP, ten vzdycky odkazuje na prvni volne misto na halde; ukazatel
    // lSecondPhaseHP ukazuje na prave zpracovavany objekt / pole; prochazeni konci ve chvili, kdy lSecondPhaseHP == lNewHeap

    ObjectTableElem* lSecondPhaseHP = lNewHeap;
    
    #if DEBUG_GC_TIME==1
        clock_t lClockSpaghettiPulling1 = clock();
    #endif

    StackElem * src;
    StackElem * dst = dst_heap;

    // Zatim mam zkopirovane jenom servisni informace, nikoliv samotna data.
    // Pro kazdy prvek nove haldy zkopiruju data, upravim pointery a projdu zkopirovana data, jestli nahodou
    // neobsahuji reference na dalsi objekty / pole. Pokud ano, tak zkopiruju jejich servisni informace
    // (pokud jeste nejsou), k datum se dostanu pozdeji.
    // A pozor na pripady, kdy uz je to presunuty.

    size_t elems_copied = 0;

    while(lSecondPhaseHP != lNewHP)
    {
        if(lSecondPhaseHP->type == Object || lSecondPhaseHP->type == ArrayContents || lSecondPhaseHP->type == StringRef)
        {
            // tady zkopiruj vlastni data...
            StackElem * limit;
            
            switch(lSecondPhaseHP->type)
            {
                case Object:
                    limit = lSecondPhaseHP->array + lSecondPhaseHP->fields->size();
                    break;
                case ArrayContents:
                    limit = lSecondPhaseHP->array + lSecondPhaseHP->capacity;
                    break;
                case StringRef:
                    // capacity je u stringu pocet alokovanych bytu (na cele StackElemy), ale my to potrebujeme prevest na pocet StakElemu
                    // Pozor prasarna: melo by se spis pouzit ObjectTableElem::string, ale to je pointer na char* a prekladaci to vadi,
                    // tak vyuzijeme toho, ze to je ve stejnem unionu jako ObjectTableElem::array, takze by to melo mit stejnou hodnotu.
                    // Ale je to fuj.
                    limit = lSecondPhaseHP->array + (lSecondPhaseHP->capacity / sizeof(StackElem));
                    break;
            }

            // Pozor stejna prasarna pro stringy jako o kousek vys.
            src = lSecondPhaseHP->array;
            ptrdiff_t distance = limit - lSecondPhaseHP->array;
            memcpy(dst, src, distance * sizeof(StackElem));
            elems_copied += distance;

            // nezapomenout na pointer na data
            lSecondPhaseHP->array = dst;

            dst += distance;
            
            // tady projdeme obsah tech puvodnich dat a pokud tam jsou nejake reference, zkopirujeme jejich servisni informace,
            // data se dostanou na radu pozdeji
            // cili tady se prochazi obsah fieldu, pokud je to objekt, nebo obsah pole; v pripade stringu nic, ty nemuzou obsahovat
            // zadna dalsi data :-)
            if(lSecondPhaseHP->type != StringRef)
            {
                for (StackElem * e = src; e != limit; ++e)
                {
                    if (e->type == ObjRef || e->type == ArrayRef || e->type == StringRef)
                    {
                        if(e->type == ObjRef && !((*e->object)->GCIsForwarded))
                        {
                            *lNewHP = **(e->object);
                            (*e->object)->GCIsForwarded = true;
                            (*e->object)->GCForwardedTo = lNewHP;
                            lNewHP++;
                        }
                        else if(e->type == ArrayRef && !((*e->array)->GCIsForwarded))
                        {
                            *lNewHP = **(e->array);
                            (*e->array)->GCIsForwarded = true;
                            (*e->array)->GCForwardedTo = lNewHP;
                            lNewHP++;
                        }
                        else if(e->type == StringRef && !((*e->string)->GCIsForwarded))
                        {
                            *lNewHP = **(e->string);
                            (*e->string)->GCIsForwarded = true;
                            (*e->string)->GCForwardedTo = lNewHP;
                            lNewHP++;
                        }
                    }
                }
            }

        }

        lSecondPhaseHP++;
    }

    alloc_ptr = dst;
    
    #if DEBUG_GC_TIME==1
        clock_t lClockSpaghettiPulling2 = clock();
        fSpaghettiPullingClock += (lClockSpaghettiPulling2 - lClockSpaghettiPulling1);
    #endif

    // 3. faze - procisteni tabulky referenci; tam se zaroven provede update pointeru tak, aby z tabulky vedly pointery na prezivsi
    // objekty do nove haldy a ne do stare
    // Toto je treba udelat jeste pred smazanim stare haldy.

    #if DEBUG_GC_TIME==1
        clock_t lRefTableCleanClock1 = clock();
    #endif

    obj_table.GCCleanUp();

    #if DEBUG_GC_TIME==1
        clock_t lRefTableCleanClock2 = clock();
        fRefTableCleanClock += (lRefTableCleanClock2 - lRefTableCleanClock1);
    #endif

    allocs_since_gc = 0;
    insns_since_gc = 0;

    #if DEBUG_GC
        int lOldHeapSize = ref_table_ptr - src_ref_table;
        int lNewHeapSize = lNewHP - lNewHeap;

        cout << "GC released " << ((lOldHeapSize - lNewHeapSize) * sizeof(ObjectTableElem)) +
            (elems_copied * sizeof(StackElem)) << " bytes." << endl;
    #endif

    #if DEBUG_GC_TIME==1
        clock_t lClockDel1 = clock();
    #endif

    CleanRefTable();
    
    #if DEBUG_GC_TIME==1
        clock_t lClockDel2 = clock();
        fDeletePart1Clock += (lClockDel2 - lClockDel1);
    #endif
        
    #if DEBUG_GC_TIME==1
        lClockDel1 = clock();
    #endif

    //delete [] src_ref_table;
    
    #if DEBUG_GC_TIME==1
        lClockDel2 = clock();
        fDeletePart2Clock += (lClockDel2 - lClockDel1);
        fTotalGCRuns++;
    #endif
        
    //src_ref_table = lNewHeap;
    swap(dst_ref_table, src_ref_table);
    ref_table_ptr = lNewHP;

    swap(dst_heap, src_heap);

    obj_table_end = src_ref_table + DefaultHeapSize;
}

// Musime taky smazat samotna data na halde...
// ... ale pozor, jenom v pripade, ze to je skutecne garbage!
// Pri kopirovani do nove haldy se data kopiruji melkou kopii, cili objekt v nove halde bude mit stejne pointery na data
// jako ten puvodni - a pri mazani puvodniho se to prave musi zkontrolovat a mazat se ma jenom v pripade, kdy je to smeti, ktere v nove
// halde neni.
// Ono by to slo delat i destruktorem v HeapElem, ale merenim jsem zjistil, ze tohle je zhruba 3x rychlejsi (to uz je dost).
void Interpreter::CleanRefTable()
{
    ObjectTableElem* lIterator = src_ref_table;

    while(lIterator != ref_table_ptr)
    {
        if(!lIterator->GCIsForwarded)
        {
            if(lIterator->type == Object)
            {
                lIterator->fields = NULL;
            }
            else if(lIterator->type == ArrayContents)
            {
                lIterator->array = NULL;
            }
        }

        lIterator++;
    }
}

int Interpreter::Run(int argc, char ** argv)
{
    int index;
    int count;
    pc = exit_pc;
    sp = stack;
    fp = NULL;
    ref_table_ptr = src_ref_table;

    try
    {
        PrepareMainArguments(argc, argv);
        FunctionCall(entry_point, 2); // call main
        do
        {
            if(ShouldPerformGC())
            {
                GC();
            }

            switch (*pc++)
            {
            case NOP:
                INSTR_TRACE("NOP", "");
                break;
            case ADD:
                Add();
                break;
            case SUB:
                Subtract();
                break;
            case MUL:
                Multliply();
                break;
            case DIV:
                Divide();
                break;
            case MOD:
                Modulus();
                break;
            case AND:
                And();
                break;
            case OR:
                Or();
                break;
            case EQL:
                Equal();
                break;
            case NEQL:
                NotEqual();
                break;
            case LT:
                LessThan();
                break;
            case GT:
                GreaterThan();
                break;
            case LE:
                LessOrEqual();
                break;
            case GE:
                GreaterOrEqual();
                break;
            case NEG:
                Negation();
                break;
            case MINUS:
                UnaryMinus();
                break;
            case GETLOCAL:
                GetLocal(GetInc<signed char>(pc));
                break;
            case SETLOCAL:
                SetLocal(GetInc<signed char>(pc));
                break;
            case GETARRAYVALUE:
                GetArrayValue();
                break;
            case SETARRAYVALUE:
                SetArrayValue();
                break;
            case GETFIELDVALUE:
                GetFieldValue(GetInc<int>(pc));
                break;
            case SETFIELDVALUE:
                SetFieldValue(GetInc<int>(pc));
                break;
            case ICONST:
                IntConst(GetInc<int>(pc));
                break;
            case SCONST:
                StringConst(GetInc<int>(pc));
                break;
            case FCALL:
                index = GetInc<int>(pc);
                count = GetInc<char>(pc);
                FunctionCall(index, count);
                break;
            case ECALL:
                index = GetInc<int>(pc);
                count = GetInc<char>(pc);
                BuiltInCall(index, count);
                break;
            case MCALL:
                index = GetInc<int>(pc);
                count = GetInc<char>(pc);
                MethodCall(index, count);
                break;
            case NEW:
                index = GetInc<int>(pc);
                count = GetInc<char>(pc);
                New(index, count);
                break;
            case FRAME:
                Frame(GetInc<char>(pc));
                break;
            case RET:
                Return();
                break;
            case RETVALUE:
                ReturnValue();
                break;
            case JT:
                JumpIfTrue(GetInc<int>(pc));
                break;
            case JF:
                JumpIfFalse(GetInc<int>(pc));
                break;
            case JMP:
                Jump(GetInc<int>(pc));
                break;
            default:
                throw runtime_error("Illegal instruction!");
            }

            ++insns_since_gc;
        } while (pc != exit_pc);

        #if DEBUG_GC_TIME==1
            cout << "Total GC runs: " << fTotalGCRuns << endl;
            cout << "Deleting - part 1 (delete data) - ticks: " << fDeletePart1Clock << "; seconds: " << ((double) fDeletePart1Clock)/CLOCKS_PER_SEC << endl;
            cout << "Deleting - part 2 (deallocate heap) - ticks: " << fDeletePart2Clock << "; seconds: " << ((double) fDeletePart2Clock)/CLOCKS_PER_SEC << endl;
            cout << "Root set construction - ticks: " << fRootSetSearchClock << "; seconds: " << ((double) fRootSetSearchClock)/CLOCKS_PER_SEC << endl;
            cout << "Spaghetti pulling - ticks: " << fSpaghettiPullingClock << "; seconds: " << ((double) fSpaghettiPullingClock)/CLOCKS_PER_SEC << endl;
            cout << "RefTable cleanup - ticks: " << fRefTableCleanClock << "; seconds: " << ((double) fRefTableCleanClock)/CLOCKS_PER_SEC << endl;
        #endif

        return static_cast<int>(sp->value);
    }
    catch (std::exception& e)
    {
        cerr << "Error: " << e.what() << '\n';
        PrintStackTrace();
        return 1;
    }

}

void Interpreter::Add()
{
    BOP_TRACE("ADD");
    CHECK(TOS->type == Number && TOS1->type == Number, "Cannot add non-numbers!")
    {
        BOP_COMMUTATIVE(+=);
    }
}

void Interpreter::Subtract()
{
    BOP_TRACE("SUB");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot subtract non-numbers!")
    {
        BOP(-);
    }
}

void Interpreter::Multliply()
{
    BOP_TRACE("MUL");
    CHECK(TOS->type == Number && TOS1->type == Number, "Cannot multiply non-numbers!")
    {
        BOP_COMMUTATIVE(*=);
    }
}

void Interpreter::Divide()
{
    BOP_TRACE("DIV");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot divide non-numbers!")
    {
        BOP(/);
    }
}

inline void Interpreter::Modulus()
{
    BOP_TRACE("MOD");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot mod non-numbers!")
    {
        BOP(%);
    }
}

inline void Interpreter::And()
{
    BOP_TRACE("AND");
    CHECK(TOS->type == Number && TOS1->type == Number, "Cannot and non-numbers!")
    {
        BOP_COMMUTATIVE(&=);
    }
}

inline void Interpreter::Or()
{
    BOP_TRACE("OR");
    CHECK(TOS->type == Number && TOS1->type == Number, "Cannot or non-numbers!")
    {
        BOP_COMMUTATIVE(|=);
    }
}


inline void Interpreter::Equal()
{
    BOP_TRACE("EQL");
    --sp;
    // musi byt stejne typy (klidne i reference)
    CHECK(TOS->type == TOSP1->type, "Cannot do == on incomatible types!")
    {
        CMP_STACK_TOP(==);
    }
}

inline void Interpreter::NotEqual()
{
    BOP_TRACE("NEQL");
    --sp;
    // musi byt stejne typy (klidne i reference)
    CHECK(TOS->type == TOSP1->type, "Cannot do != on incomatible types!")
    {
        CMP_STACK_TOP(!=);
    }
}

inline void Interpreter::LessThan()
{
    BOP_TRACE("LT");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot do < on non-numbers!")
    {
        CMP_STACK_TOP(<);
    }
}

void Interpreter::GreaterThan()
{
    BOP_TRACE("GT");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot do > on non-numbers!")
    {
        CMP_STACK_TOP(>);
    }
}

void Interpreter::LessOrEqual()
{
    BOP_TRACE("LE");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot do <= on non-numbers!")
    {
        CMP_STACK_TOP(<=);
    }
}

inline void Interpreter::GreaterOrEqual()
{
    BOP_TRACE("GE");
    --sp;
    CHECK(TOS->type == Number && TOSP1->type == Number, "Cannot do >= on non-numbers!")
    {
        CMP_STACK_TOP(>=);
    }
}

inline void Interpreter::Negation()
{
    BOP_TRACE("NEG");
    CHECK(TOS->type == Number, "Cannot negate a non-number!")
    {
        TOS->value = !TOS->value;
    }
}

inline void Interpreter::UnaryMinus()
{
    BOP_TRACE("MINUS");
    CHECK(TOS->type == Number, "Cannot make a non-number opposite!")
    {
        TOS->value = -TOS->value;
    }
}

inline void Interpreter::GetLocal(int i)
{
    // primo kopie na posunuty vrchol zas., neni to C krasne? :-)
    *(++sp) = *(fp + i);
    INSTR_TRACE("GETLOCAL", i << ' ' << *TOS);
}

inline void Interpreter::SetLocal(int i)
{
    INSTR_TRACE("SETLOCAL", i << ' ' << *TOS);
    // zapis z vrcholu stacku s naslednym posunem sp
    *(fp + i) = *sp--;
}

inline void Interpreter::GetArrayValue()
{
    INSTR_TRACE("GETARRAY", *TOS << '[' << *TOS1 << "] = " << (*TOS->array)->array[TOS1->value]);
    CHECK(TOS->type == ArrayRef, "Cannot get element of non-array")
    {
        // na vrcholu ref na pole, pred nim index
        --sp;   // rovnou se posunu na cilovou adresu
        // zapisu hodnotu z pole
        *sp = (*TOSP1->array)->array[TOS->value];

        // kontrola, jestli ma prvek pole definovanou hodnotu
        // je lepsi to udelat uz tady, nez kdyby to spadlo s nejakou nicnerikajici
        // hlaskou nekde pozdeji
        CHECK(TOS->type != Undefined, "Array element is undefined") { }
    }
}

inline void Interpreter::SetArrayValue()
{
    INSTR_TRACE("SETARRAY", *TOS << '[' << *TOS1 << "] = " << *TOS2);
    CHECK(TOS->type == ArrayRef, "Cannot set element of non-array")
    {
        // na vrcholu ref na pole, pred nim index a pred nim hodnota
        (*TOS->array)->array[TOS1->value] = *TOS2;
        sp -= 3;    // smazu stopy
    }
}

inline void Interpreter::GetFieldValue(int i)
{
    INSTR_TRACE("GETFIELD", *TOS << '.' << pool[i]);
    CHECK(TOS->type == ObjRef, "Cannot get field of non-object")
    {
        // this na vrcholu zas., rovnou ho prepisu obsahem fieldu
        *sp = (*TOS->object)->array[(*TOS->object)->fields->at(i)];
    }
}

inline void Interpreter::SetFieldValue(int i)
{
    INSTR_TRACE("SETFIELD", *TOS << '.' << pool[i] << " = " << *TOS1);
    CHECK(TOS->type == ObjRef, "Cannot set field of non-object")
    {
        // this na vrcholu zas., pred nim index fieldu - najdu a zapisu

        (*TOS->object)->array[(*TOS->object)->fields->at(i)] = *TOS1;
        sp -= 2;    // smazu stopy
    }
}

inline void Interpreter::IntConst(int val)
{
    INSTR_TRACE("ICONST", val);
    ++sp;
    TOS->type = Number;
    TOS->value = val;
}

inline void Interpreter::StringConst(int i)
{
    INSTR_TRACE("SCONST", '"' << (pool[i].length() > 20 ? pool[i].substr(0, 17) + string("...") : pool[i]) << '"');
    ++sp;
    //TOS->type = StringRef;
    //TOS->string = &pool[i].c_str();
    *sp = StackElem(AllocateString(0));

    // bacha co kdyz je to prazdny string - pristup na index 0 vyhodi vyjimku
    if(pool[i].length() == 0)
        (*sp->string)->string = "";
    else
        (*sp->string)->string = &pool[i][0];
}

inline void Interpreter::FunctionCall(int addr, int params)
{
    CALL_TRACE("FCALL", AddrToName(bytecode + addr) << '(' << params - 1 << " args)");
    PushRetAddr();
    pc = bytecode + addr;   // skok rovnou do tela funkce
}

inline void Interpreter::MethodCall(int i, int params)
{
    CALL_TRACE("MCALL",
            AddrToName((*TOS->object)->vtable->at(VTable::key_type(i, params)))
            << '(' << params - 2 << " args) (" << *TOS << ')');
    CHECK(TOS->type == ObjRef, "Cannot call method on non-object")
    {
        PushRetAddr();
        // this je na zasobniku pred RA (sp ukazuje na RA), najdu k nemu metodu a skocim na ni
        pc = (*TOS1->object)->vtable->at(VTable::key_type(i, params));
    }
}

inline void Interpreter::BuiltInCall(int i, int params)
{
    CALL_TRACE("ECALL", pool[i] << '(' << params << " args)");
    (this->*built_ins.at(i))(params);      // zavola built in funkci nabindovanou na jmeno s indexem i
    ERET_TRACE("ERET", "");
}

inline void Interpreter::New(int i, int params)
{
    CALL_TRACE("NEW", pool[i] + "::" + pool[i] << '(' << params - 2 << " args)");
    Class& c(classes.at(i));       // najdu tridu podle jmena
    
    EOHCHECK;

    ObjectTableElem ** obj = AllocateObject(c);

    ++sp;
    TOS->type = ObjRef;       // this vyplnim referenci
    TOS->object = obj;

    PushRetAddr();
    pc = c.vtable.at(VTable::key_type(i, params));
}

inline void Interpreter::Frame(int count)
{
    INSTR_TRACE("FRAME", count);
    ++sp;                       // zaloha aktualniho frame pointeru
    TOS->type = FramePointer;    //
    TOS->backup_fp = fp;         //
    fp = sp;                    // z aktualniho stack pointeru se stane frame pointer
    sp += count;                // misto pro lokalni promenne
}

inline void Interpreter::Return()
{
    RET_TRACE("RET", "");
    CHECK((fp - 1)->type == ReturnAddress, "Cannot Return - no return address on stack!")
    {
        pc = (fp - 1)->ret_addr;    // obnoveni RA ze zasobniku
        // z bytecodu mista volani se precte pocet parametru ke smazani, -1 je smazani RetAddr
        sp = fp - Get<char>(pc - 1) - 1;
        fp = fp->backup_fp;                 // obnova fp
    }
}

inline void Interpreter::ReturnValue()
{
    RET_TRACE("RETVAL", *TOS);
    CHECK((fp - 1)->type == ReturnAddress, "Cannot Return value - no return address on stack!")
    {
        pc = (fp - 1)->ret_addr;    // obnoveni RA
        StackElem * new_sp = fp - Get<char>(pc - 1);    // posun sp
        *new_sp = *sp;              // presun navratove hodnoty na novy vrchol zasobniku
        sp = new_sp;
        fp = fp->backup_fp;         // obnova fp
    }
}

inline void Interpreter::JumpIfTrue(int offset)
{
    INSTR_TRACE("JT", offset);
    CHECK(TOS->type == Number, "Cannot JumpIfTrue - top of stack does not contain a boolean value!")
    {
        if (TOS->value)
        {
            pc += offset;
        }
        --sp;
    }
}

inline void Interpreter::JumpIfFalse(int offset)
{
    INSTR_TRACE("JF", offset);
    CHECK(TOS->type == Number, "Cannot JumpIfFalse - top of stack does not contain a boolean value!")
    {
        if (!TOS->value)
        {
            pc += offset;
        }
        --sp;
    }
}

inline void Interpreter::Jump(int offset)
{
    INSTR_TRACE("JMP", offset);
    pc += offset;
}

void Interpreter::PrepareMainArguments(int argc, char** argv)
{
    argc--;
    argv++;
    *(++sp) = StackElem(argc);
    *(++sp) = StackElem(argc);
    Array(1);
    for (int i = 0; (i < argc) && argv[i]; ++i)
    {
        stringstream ss(argv[i]);
        int val;
        ss >> val;
        if (ss.fail())
        {
            ObjectTableElem ** str = AllocateString(0);
            (*str)->string = argv[i];
            (*TOS->array)->array[i] = StackElem(str);
        }
        else
        {
            (*TOS->array)->array[i].type = Number;
            (*TOS->array)->array[i].value = val;
        }
    }
}

inline void Interpreter::PushRetAddr()
{
    ++sp;
    TOS->ret_addr = pc;
    TOS->type = ReturnAddress;
}

void Interpreter::Print(int params)
{

    for (StackElem * s = sp - (params - 1); s <= sp; ++s)
    CHECK(s->type == Number || s->type == StringRef, "print() can print only numbers and strings!")
    switch (s->type)
    {
    case Number:
        cout << s->value;
        break;
    case StringRef:
        cout << (*s->string)->string;
        break;
    default:
        break;
    }
    sp -= params;
}

void Interpreter::PrintLn(int params)
{
    Print(params);
    cout << endl;
}

StackElem * Interpreter::Allocate(IntType count)
{
    if (alloc_ptr + count > src_heap + DefaultHeapElems)
    {
        GC();
        if (alloc_ptr + count > src_heap + DefaultHeapElems)
            throw runtime_error("Cannot allocate, out of memory!");
    }

    StackElem * ret = alloc_ptr;
    alloc_ptr += count;
    ++allocs_since_gc;
    return ret;
}

ObjectTableElem ** Interpreter::AllocateObject(const Class& c)
{
    IntType fields = c.field_offsets.size();
    StackElem * arr = Allocate(fields);
    ref_table_ptr->type = Object;
    ref_table_ptr->array = arr;
    ref_table_ptr->fields = &c.field_offsets;
    ref_table_ptr->vtable = &c.vtable;
    if(fields > 0)
        memset(arr, 0, sizeof(arr[0]) * fields);

    return obj_table.AddReference(ref_table_ptr++);
}

ObjectTableElem ** Interpreter::AllocateArray(IntType elems)
{
    StackElem * arr = Allocate(elems);
    ref_table_ptr->type = ArrayContents;
    ref_table_ptr->array = arr;
    ref_table_ptr->capacity = elems;

    if(elems > 0)
        memset(arr, 0, sizeof(arr[0]) * elems);

    return obj_table.AddReference(ref_table_ptr++);
}

void Interpreter::ReallocateArray(ObjectTableElem& array)
{
    StackElem * new_arr = Allocate(array.capacity * 2);
    memcpy(new_arr, array.array, sizeof(array.array[0]) * array.capacity);
    array.capacity *= 2;
    array.array = new_arr;
}

ObjectTableElem ** Interpreter::AllocateString(IntType len)
{
    IntType len_stack_elems = (len + sizeof(StackElem) - 1) / sizeof(StackElem);
    StackElem * s = Allocate(len_stack_elems);
    ref_table_ptr->type = StringRef;
    ref_table_ptr->string = reinterpret_cast<char *>(s);
    ref_table_ptr->size = len;
    ref_table_ptr->capacity = len_stack_elems * sizeof(StackElem);
    return obj_table.AddReference(ref_table_ptr++);
}

ObjectTableElem ** Interpreter::AllocateArrayOfStrings(const std::vector<std::string>& strings)
{
    ObjectTableElem ** a = AllocateArray(static_cast<IntType>(strings.size()));
    ObjectTableElem& arr = **a;
    // musime inicializovat velikost, AllocateArray to nedela (z dobrych duvodu)
    arr.size = 0;
    for (vector<string>::const_iterator it = strings.begin(); it != strings.end(); ++it)
    {
        ObjectTableElem ** str = AllocateString(static_cast<IntType>(it->length() + 1));
        memcpy((*str)->string, it->c_str(), it->length() + 1);
        arr.array[arr.size++] = StackElem(str);
    }
    return a;
}

void Interpreter::Array(int params)
{
    CHECK(params == 0 || (params == 1 && TOS->type == Number), "array() expects one integral argument!")
    {
        EOHCHECK;

        IntType size, capacity;
        if (params == 0)
        {
            ++sp;
            capacity = 4;
            size = 0;
        }
        else
        {
            size = capacity = TOS->value;
        }
        
        TOS->type = ArrayRef;
        TOS->array = AllocateArray(capacity);
        (*TOS->array)->size = size;
    }
}

void Interpreter::ArraySize(int params)
{
    CHECK(params == 1 && TOS->type == ArrayRef, "array_push() expects array ref and an item!")
    {
        *TOS = StackElem((*TOS->array)->size);
    }
}

void Interpreter::ArrayPush(int params)
{
    CHECK(params == 2 && TOS1->type == ArrayRef, "array_push() expects array ref and an item!")
    {
        ObjectTableElem& array = **TOS1->array;

        if (array.size == array.capacity)
            ReallocateArray(array);

        array.array[array.size++] = *sp;
        sp -= 2;
    }
}

void Interpreter::Exit(int params)
{
    CHECK(params == 1 && TOS->type == Number, "exit() expects an integral exit code!")
    {
        stack[1] = *sp;
        pc = exit_pc;
    }
}

void Interpreter::ParseInt(int params)
{
    CHECK(params == 1 && TOS->type == StringRef, "parse_int() expects a string ref!")
    {
        *TOS = StackElem(strtol((*TOS->string)->string, NULL, 10));
    }
}

void Interpreter::ReadLines(int params)
{
    CHECK(params == 1 && TOS->type == StringRef, "read_lines() expects a string ref (filename)!")
    {
        EOHCHECK;

        ifstream in((*TOS->string)->string);

        vector<string> lines;

        /*hp->type = ArrayContents;
        hp->array = new ::Array();

        TOS->type = ArrayRef;
        TOS->array = obj_table.AddReference(hp);

        ++hp;
        ++allocs_since_gc;*/

        TOS->type = ArrayRef;

        if (!in)
        {
            TOS->array = AllocateArray(0);
            return;
        }

        string line;

        while(getline(in, line))
        {
            lines.push_back(line);
            //(*TOS->array)->array->push_back(StackElem(new string(line)));
        }

        TOS->array = AllocateArrayOfStrings(lines);
    }
}

void Interpreter::SplitString(int params)
{
    CHECK(params == 2 && TOS->type == StringRef && TOS1->type == StringRef, "string_split() expects two string refs!")
    {
        EOHCHECK;
        const char * delims = (*TOS->string)->string;
        --sp;
        string str((*TOS->string)->string);   // kopie - strtok zapisuje do stringu '\0'

        /*hp->type = ArrayContents;
        hp->array = new ::Array();

        TOS->type = ArrayRef;
        TOS->array = obj_table.AddReference(hp);
        ++hp;
        ++allocs_since_gc;*/

        vector<string> elems;

        TOS->type = ArrayRef;
        
        char * p = strtok(&str[0], delims);
        while (p)
        {
            //(*TOS->array)->array->push_back(StackElem(new string(p)));
            elems.push_back(string(p));
            p = strtok(NULL, delims);
        }
        TOS->array = AllocateArrayOfStrings(elems);
    }
}

void Interpreter::AddBuiltInFunction(const std::string& name, BuiltInFunction f)
{
    UndefinedFunctions::const_iterator it = undefs.find(name);
    if (it != undefs.end())
        built_ins.insert(BuiltInFunctions::value_type(it->second, f));
}

void Interpreter::BindBuiltIns()
{
    AddBuiltInFunction("print", &Interpreter::Print);
    AddBuiltInFunction("println", &Interpreter::PrintLn);
    AddBuiltInFunction("array", &Interpreter::Array);
    AddBuiltInFunction("array_push", &Interpreter::ArrayPush);
    AddBuiltInFunction("array_size", &Interpreter::ArraySize);
    AddBuiltInFunction("exit", &Interpreter::Exit);
    AddBuiltInFunction("parse_int", &Interpreter::ParseInt);
    AddBuiltInFunction("read_lines", &Interpreter::ReadLines);
    AddBuiltInFunction("string_split", &Interpreter::SplitString);
}

const std::string& Interpreter::AddrToName(Bytecode addr)
{
    return (--addr_to_name.upper_bound(addr))->second;
}

void Interpreter::PrintStackTrace()
{
    cerr << "============\n"
            "Stack Trace:\n  "
         << AddrToName(pc) << '\n';
    StackElem * s = sp;
    do
    {
        if (s->type == ReturnAddress)
            cerr << "  " << AddrToName(s->ret_addr) << '\n';
    } while (--s != stack + 3);
    cerr << "============\n";
}
